package leetcode.lt100;

class Solution_44 {
	public boolean isMatch(String s, String p) {
		
		//去除多余的*号
		

		// 动态规划,dp[i][j]表示记录s截取长度为i的字符串和p截取长度j的字符串是否满足匹配要求
		boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];

		// 设置初始状态,都为0时为true
		dp[0][0] = true;

		// 处理特殊情况,例如s="adceb";p="*a*b"
		while (p.length() > 0 && p.charAt(0) == '*')
			dp[0][1] = true;

		for (int i = 1; i <= s.length(); i++) {
			for (int j = 1; j <= p.length(); j++) {
				// 如果p的j-1位为*,则有三种情况
				// 1.dp[i-1][j-1]为true表示s长度为i-1的前部分和p长度为j-1的前部分满足匹配要求,则只需要使新的一位字符匹配*,显然满足
				// 2.dp[i -
				// 1][j]为true表示s长度为i-1的前部分和p长度为j的前部分满足匹配要求,因为*可以匹配任意位数任意字符,显然也满足
				// 3.dp[i][j -
				// 1]为true表示s长度为i的前部分和p长度为j-1的前部分满足匹配要求,因为*可以匹配空字符串,所以也应满足
				if (p.charAt(j - 1) == '*') {
					dp[i][j] = dp[i - 1][j - 1] || dp[i - 1][j] || dp[i][j - 1];
				} else {
					// 如果p的j-1位不为*,则只有在s长度为i的前部分和p长度为j-1的前部分满足匹配要求并且s和p新的一位相等或p新的一位为?才满足匹配要求
					dp[i][j] = dp[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?');
				}
			}
		}

		return dp[s.length()][p.length()];
	}
}